public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];

        //预处理前缀积和后缀积数组
        f[0] = g[n-1] = 1;
        for(int i = 1; i < n; i++)
            f[i] = f[i-1] * nums[i-1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i+1] * nums[i+1];

        int[] ret = new int[n];
        for(int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];
        return ret;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 2, 3, 4};
        int[] result1 = solution.productExceptSelf(nums1);
        System.out.print("Input: [1, 2, 3, 4], Output: [");
        for (int i = 0; i < result1.length; i++) {
            System.out.print(result1[i]);
            if (i < result1.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}
